// 1. 两个数组的交集_无序版
use std::collections::HashMap;

pub fn intersect(n1: Vec<i32>, n2: &mut Vec<i32>) -> Vec<i32> {
    let mut res: HashMap<i32, i32> = HashMap::new();
    let mut k = 0;
    for v in n1 {
        let counter = res.entry(v).or_insert(0);
        *counter += 1;
    }
    for i in 0..n2.len() {
        let v = n2[i];
        if let Some(c) = res.get_mut(&v) {
            if *c > 0 {
                n2[k] = v;
                *c -= 1;
                k += 1;
            }
        }
    }
    n2[0..k].to_vec()
}

//1.2 两个数组的集合_有序版
pub fn intersect_v2(n1: Vec<i32>, n2: &mut Vec<i32>) -> Vec<i32> {
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;
    while i < n1.len() && j < n2.len() {
        if n1[i] > n2[j] {
            j += 1;
        } else if n1[i] < n2[j] {
            i += 1;
        } else {
            n2[k] = n1[i];
            i += 1;
            j += 1;
            k += 1;
        }
    }
    n2[0..k].to_vec()
}

//2. 最长公共前缀
pub fn longest_common_prefix(strs: Vec<&str>) -> String {
    if strs.len() < 1 {
        return "".to_string();
    }
    let mut prefix = strs[0];
    for v in strs[1..].iter() {
        while !(v.starts_with(prefix)) {
            if prefix != "" {
                prefix = prefix.get(..(prefix.len() - 1)).unwrap();
            } else {
                return "".to_string();
            }
        }
    }
    prefix.to_string()
}

// 3. 买卖股票的最佳时机
pub fn max_profit(prices: Vec<i32>) -> i32 {
    if prices.len() < 2 {
        return 0;
    }
    let mut profit = 0;
    let mut temp = prices[0];
    for price in prices[1..].iter() {
        let diff = price - temp;
        if diff > 0 {
            profit += diff;
        }
        temp = *price;
    }
    profit
}

// 4. 旋转数组
pub fn rotate(nums: &mut Vec<i32>, k: usize) -> Vec<i32> {
    nums.reverse();
    nums[..k].reverse();
    nums[k..].reverse();
    nums.to_vec()
}

// 5. 原地删除指定元素
pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> Vec<i32> {
    let mut i = 0;
    let mut j = nums.len() - 1;
    while i < j {
        if nums[i] == val {
            while nums[j] == val && i < j {
                j -= 1;
            }
            if i < j {
                nums[i] = nums[j];
                nums[j] = val;
                j -= 1;
                i += 1;
            }
        } else {
            i += 1;
        }
    }
    nums[..=i].to_vec()
}

// 6. 加一
pub fn plus_one(digits: &mut Vec<i32>) -> Vec<i32> {
    for i in (0..digits.len()).rev() {
        digits[i] += 1;
        if digits[i] < 10 {
            break;
        } else {
            digits[i] = 0;
        }
    }
    if digits[0] == 0 {
        digits.insert(0, 1);
    }
    digits.to_vec()
}

// 7. 两数之和
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<usize> {
    let hm = nums
        .iter()
        .enumerate()
        .map(|(index, value)| (*value, index))
        .collect::<HashMap<i32, usize>>();
    let mut res = vec![];
    for i in 0..nums.len() {
        if let Some(_index) = hm.get(&(target - nums[i])) {
            res.push(i);
        }
    }
    res
}
